package q56_merge;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        // int[][] arr1 = new int[][]{{4,8}, {1,2}, {7,8}};
        int[][] arr1 = new int[][]{{4,8}};
        int[][] arr = s.merge(arr1);

//        for (int[] ins : arr) {
//            System.out.println(Arrays.toString(ins));
//        }
    }

    public int[][] merge(int[][] intervals) {

        // 重写Arrays中的sort方法，可以对任意的对象数组进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // 这一语句是在如果起点相同的情况下，再按照终点进行排序，可以不要
                // if (o1[0]==o2[0]) return o1[1]-o2[1];
                return o1[0] - o2[0];
            }
        });

        /**
         * 这是个人的解法，使用了部分多余变量
         */
//        List<int[]> list = new ArrayList<int[]>();
//        int[] A = intervals[0];
//        list.add(A);
//
//        int mergeCount = 0;
//        for (int i = 1; i < intervals.length ; i++) {
//            if (A[1] < intervals[i][0]){
//                list.add(intervals[i]);
//                A = intervals[i];
//            }else {
//                A[1] = Math.max(A[1],intervals[i][1]);
//                mergeCount++;
//                list.set(i - mergeCount,A);
//
//            }
//        }
//
//        int[][] arr = list.toArray(new int[0][]);
//
//        for (int i = 0; i < arr.length; i++) {
//            System.out.println(Arrays.toString(arr[i]));
//        }
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            // 存储当前的范围左右位置
            int L = intervals[i][0], R = intervals[i][1];
            // 如果merged还没有元素，那么先添加
            // 或者merged中 *（最后一个）*的范围右侧比当前的元素左侧小，意味着要加入当前的这个元素
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                // 另一种情况就是需要合并，显然合并的时候一定是最后一个元素与当前元素进行范围合并
                // 所以只需要使用get方法得到最后一个元素，并设置其右边的范围即可
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }


        return merged.toArray(new int[merged.size()][]);
    }
}
